#![allow(dead_code)]
use std::cmp::{max, min};
use std::collections::{HashMap, HashSet, VecDeque};

type TreeLink = Option<Box<TreeNode>>;
#[allow(dead_code)]
type TreeNodeLink<'a> = Option<&'a Box<TreeNode>>;
#[derive(Debug, Hash, PartialEq, Eq)]
struct TreeNode {
    elem: i32,
    left: TreeLink,
    right: TreeLink,
}
impl TreeNode {
    fn new(elem: i32) -> Self {
        Self {
            elem,
            left: None,
            right: None,
        }
    }
}

fn create_bitree_recursion2(node_values: &mut VecDeque<&str>) -> TreeLink {
    let val = node_values.pop_front().unwrap();
    if val == "N" {
        return None;
    }

    let mut node: TreeNode = TreeNode::new(val.parse::<i32>().unwrap());
    node.left = create_bitree_recursion2(node_values);
    node.right = create_bitree_recursion2(node_values);
    Some(Box::new(node))
}

/* 前序遍历的方式创建二叉树 */
fn create_bitree2(s: &str) -> TreeLink {
    let mut node_values: VecDeque<&str> = s.split('_').collect();
    create_bitree_recursion2(&mut node_values)
}

fn preorder_recursion(root: &TreeLink, res: &mut Vec<i32>) {
    if root.is_none() {
        return;
    }
    if let Some(node) = root {
        res.push(node.elem);
        preorder_recursion(&node.left, res);
        preorder_recursion(&node.right, res);
    }
}
fn preorder_unrecursion(root: &TreeLink) -> Vec<i32> {
    let mut res: Vec<i32> = vec![];
    let mut stack: Vec<&TreeLink> = vec![];
    stack.push(root);
    while !stack.is_empty() {
        if let Some(Some(node)) = stack.pop() {
            res.push(node.elem);
            stack.push(&node.right);
            stack.push(&node.left);
        }
    }
    res
}

fn inorder_unrecursion(root: &TreeLink) -> Vec<i32> {
    let mut res: Vec<i32> = vec![];
    let mut stack: Vec<Option<&Box<TreeNode>>> = vec![];
    let mut head = root.as_ref();

    while head.is_some() || !stack.is_empty() {
        if let Some(node) = head {
            stack.push(Some(node.clone()));
            head = node.left.as_ref();
        } else {
            if let Some(Some(node)) = stack.pop() {
                res.push(node.elem);
                head = node.right.as_ref();
            }
        }
    }

    res
}

fn posorder_unrecursion1(root: &TreeLink) -> Vec<i32> {
    let mut stack: Vec<Option<&Box<TreeNode>>> = vec![];
    let mut help: Vec<Option<&Box<TreeNode>>> = vec![];
    let head = root.as_ref();
    let mut res: Vec<i32> = vec![];

    stack.push(head);
    while !stack.is_empty() {
        if let Some(Some(node)) = stack.pop() {
            help.push(Some(node.clone()));
            stack.push(node.left.as_ref());
            stack.push(node.right.as_ref());
        }
    }
    while let Some(Some(node)) = help.pop() {
        res.push(node.elem)
    }

    res
}

fn width_traversial(root: &TreeLink) -> Vec<i32> {
    let mut queue: VecDeque<Option<&Box<TreeNode>>> = VecDeque::new();
    let head = root.as_ref();
    let mut res: Vec<i32> = vec![];
    queue.push_back(head);

    while !queue.is_empty() {
        if let Some(Some(node)) = queue.pop_front() {
            res.push(node.elem);
            queue.push_back(node.left.as_ref());
            queue.push_back(node.right.as_ref());
        }
    }
    res
}

fn test_hash() {
    let root = Some(Box::new(TreeNode::new(100)));
    let _root2 = Some(Box::new(TreeNode::new(200)));
    let mut map: HashMap<&TreeLink, i32> = HashMap::new();
    map.insert(&root, 1);
    println!("map: {:?}", map);
    let x = map.get(&root);
    println!("x:{:?}", x);
    println!("map contains: {}", map.contains_key(&root));
}

fn max_width_hash(root: &TreeLink) -> i32 {
    let mut map: HashMap<Option<&Box<TreeNode>>, usize> = HashMap::new();
    let mut queue: VecDeque<Option<&Box<TreeNode>>> = VecDeque::new();
    let mut cur_level: usize = 1;
    let mut cur_level_nodes = 0;
    let mut max_level_nodes: i32 = 0;
    queue.push_back(root.as_ref());
    map.insert(root.as_ref(), 1);

    while let Some(link) = queue.pop_front() {
        let node_level = *map.get(&link).unwrap();
        if let Some(cur) = link {
            if node_level == cur_level {
                cur_level_nodes += 1;
            } else {
                max_level_nodes = max(max_level_nodes, cur_level_nodes);
                cur_level_nodes = 1;
                cur_level += 1;
            }
            if cur.left.is_some() {
                map.insert(cur.left.as_ref(), cur_level + 1);
                queue.push_back(cur.left.as_ref());
            }
            if cur.right.is_some() {
                map.insert(cur.right.as_ref(), cur_level + 1);
                queue.push_back(cur.right.as_ref());
            }
        }
    }

    max(max_level_nodes, cur_level_nodes)
}

fn max_width_unhash(root: &TreeLink) -> i32 {
    let mut queue: VecDeque<Option<&Box<TreeNode>>> = VecDeque::new();
    let mut max_level_nodes = 0;
    let mut cur_level_nodes = 0;
    let mut cur_end: &Box<TreeNode> = root.as_ref().unwrap();
    let mut next_end: &Box<TreeNode> = root.as_ref().unwrap();
    queue.push_back(root.as_ref());

    while let Some(Some(node)) = queue.pop_front() {
        cur_level_nodes += 1;
        if node.left.is_some() {
            queue.push_back(node.left.as_ref());
            next_end = node.left.as_ref().unwrap();
        }
        if node.right.is_some() {
            queue.push_back(node.right.as_ref());
            next_end = node.right.as_ref().unwrap();
        }

        if node == cur_end {
            max_level_nodes = max(max_level_nodes, cur_level_nodes);
            cur_level_nodes = 0;
            cur_end = next_end;
        }
    }

    max_level_nodes
}

struct BtsInfo {
    isbts: bool,
    max_val: i32,
    min_val: i32,
}
impl BtsInfo {
    fn new(isbts: bool) -> Self {
        Self {
            isbts,
            max_val: i32::MIN,
            min_val: i32::MAX,
        }
    }
}
fn check_bts_recursion(root: Option<&Box<TreeNode>>) -> BtsInfo {
    if let Some(node) = root {
        let left = check_bts_recursion(node.left.as_ref());
        if !left.isbts || left.max_val >= node.elem {
            return BtsInfo::new(false);
        }

        let right = check_bts_recursion(node.right.as_ref());
        if !right.isbts || node.elem >= right.min_val {
            return BtsInfo::new(false);
        } else {
            let mut info = BtsInfo::new(true);
            info.min_val = min(node.elem, left.min_val);
            info.max_val = max(node.elem, right.max_val);
            return info;
        }
    } else {
        BtsInfo::new(true)
    }
}

fn is_bts_recursion(root: &TreeLink) -> bool {
    let info = check_bts_recursion(root.as_ref());
    info.isbts
}

fn is_leaf(node: &Box<TreeNode>) -> bool {
    if node.right.is_none() && node.left.is_none() {
        true
    } else {
        false
    }
}

fn is_cbt_unrecursion(root: &TreeLink) -> bool {
    let mut queue: VecDeque<Option<&Box<TreeNode>>> = VecDeque::new();
    queue.push_back(root.as_ref());
    let mut must_leaf: bool = false;

    while let Some(Some(node)) = queue.pop_front() {
        if node.left.is_none() && node.right.is_some() {
            return false;
        }
        if node.left.is_some() && node.right.is_none() {
            must_leaf = true;
        }
        if must_leaf && !is_leaf(node) {
            return false;
        }

        queue.push_back(node.left.as_ref());
        queue.push_back(node.right.as_ref());
    }

    true
}

fn is_fbts_unrecursion(root: &TreeLink) -> bool {
    let mut queue: VecDeque<Option<&Box<TreeNode>>> = VecDeque::new();
    let mut cur_end: &Box<TreeNode> = root.as_ref().unwrap();
    let mut next_end: &Box<TreeNode> = root.as_ref().unwrap();
    let mut deep: u32 = 0;
    let mut total_nodes: i32 = 0;
    queue.push_back(root.as_ref());

    while let Some(Some(node)) = queue.pop_front() {
        total_nodes += 1;
        if node.left.is_some() {
            queue.push_back(node.left.as_ref());
            next_end = node.left.as_ref().unwrap();
        }
        if node.right.is_some() {
            queue.push_back(node.right.as_ref());
            next_end = node.right.as_ref().unwrap();
        }

        if node == cur_end {
            cur_end = next_end;
            deep += 1;
        }
    }

    total_nodes == (1 << deep) - 1
}

struct FbtsInfo {
    nodes: i32,
    deep: u32,
}

fn fbts_recursion(root: Option<&Box<TreeNode>>) -> FbtsInfo {
    if let Some(node) = root {
        let left = fbts_recursion(node.left.as_ref());
        let right = fbts_recursion(node.right.as_ref());

        FbtsInfo {
            nodes: left.nodes + right.nodes + 1,
            deep: max(left.deep, right.deep) + 1,
        }
    } else {
        FbtsInfo { nodes: 0, deep: 0 }
    }
}

fn is_fbts_recursion(root: &TreeLink) -> bool {
    if root.is_none() {
        return true;
    }
    let info = fbts_recursion(root.as_ref());
    info.nodes == (1 << info.deep) - 1
}

struct BlInfo {
    is_balance: bool,
    deep: i32,
}

fn balance_recursion(root: Option<&Box<TreeNode>>) -> BlInfo {
    if let Some(node) = root {
        let left = balance_recursion(node.left.as_ref());
        let right = balance_recursion(node.right.as_ref());
        BlInfo {
            deep: max(left.deep, right.deep) + 1,
            is_balance: left.is_balance && right.is_balance && (left.deep - right.deep).abs() < 2,
        }
    } else {
        BlInfo {
            deep: 0,
            is_balance: true,
        }
    }
}

fn is_balance(root: &TreeLink) -> bool {
    let info = balance_recursion(root.as_ref());
    info.is_balance
}

fn get_fmap<'a: 'b, 'b>(
    root: Option<&'a Box<TreeNode>>,
    fmap: &'b mut HashMap<Option<&'a Box<TreeNode>>, Option<&'a Box<TreeNode>>>,
) {
    if root.is_none() {
        return;
    }
    if let Some(node) = root {
        if node.left.is_some() {
            fmap.insert(node.left.as_ref(), Some(node.clone()));
            get_fmap(node.left.as_ref(), fmap);
        }
        if node.right.is_some() {
            fmap.insert(node.right.as_ref(), Some(node.clone()));
            get_fmap(node.right.as_ref(), fmap);
        }
    }
}

fn find_lca_uncrusive<'a>(
    root: &'a TreeLink,
    node1: TreeNodeLink,
    node2: TreeNodeLink,
) -> Option<&'a Box<TreeNode>> {
    let mut lca: TreeNodeLink = None;
    let mut fmap: HashMap<TreeNodeLink, TreeNodeLink> = HashMap::new();
    let mut set: HashSet<TreeNodeLink> = HashSet::new();
    fmap.insert(root.as_ref(), root.as_ref());
    get_fmap(root.as_ref(), &mut fmap);
    let mut node = node1;
    while let Some(&Some(father)) = fmap.get(&node) {
        if father != root.as_ref().unwrap() {
            set.insert(Some(father.clone()));
            node = Some(father);
        } else {
            break;
        }
    }

    node = node2;
    while let Some(&Some(father)) = fmap.get(&node) {
        if father == root.as_ref().unwrap() {
            break;
        }
        if !set.contains(&Some(father)) {
            node = Some(father);
        } else {
            lca = Some(father);
            break;
        }
    }

    lca
}

fn find_node(root: &TreeLink, elem: i32) -> TreeNodeLink {
    let mut stack: Vec<TreeNodeLink> = Vec::new();
    stack.push(root.as_ref());
    while let Some(Some(node)) = stack.pop() {
        if node.elem == elem {
            return Some(node);
        }
        if node.left.is_some() {
            stack.push(node.left.as_ref());
        }
        if node.right.is_some() {
            stack.push(node.right.as_ref());
        }
    }
    None
}

fn test_lca_unrecursion() {
    let s = "1_2_0_N_N_4_6_N_N_7_N_N_3_5_8_N_N_9_N_N_N";
    let root = create_bitree2(s);
    let node1 = find_node(&root, 6);
    let node2 = find_node(&root, 0);
    let node = find_lca_uncrusive(&root, node1, node2);
    println!("除root外的公共节点(应该是2): {:?}", node);

    let node1 = find_node(&root, 6);
    let node2 = find_node(&root, 7);
    let node = find_lca_uncrusive(&root, node1, node2);
    println!("除root外的公共节点(应该是4): {:?}", node);

    let node1 = find_node(&root, 8);
    let node2 = find_node(&root, 7);
    let node = find_lca_uncrusive(&root, node1, node2);
    println!("除root外的公共节点(应该是None): {:?}", node);
}

fn find_lca_recursion<'a>(
    root: TreeNodeLink<'a>,
    node1: TreeNodeLink<'a>,
    node2: TreeNodeLink<'a>,
) -> TreeNodeLink<'a> {
    if root.is_none() || root == node1 || root == node2 {
        return root;
    }
    if let Some(node) = root {
        let left = find_lca_recursion(node.left.as_ref(), node1, node2);
        let right = find_lca_recursion(node.right.as_ref(), node1, node2);
        match (left, right) {
            (Some(_), Some(_)) => return root,
            (Some(l), _) => return Some(l),
            (None, Some(r)) => return Some(r),
            (None, None) => return None,
        }
    }
    None
}

/*
fn left_leaf(root: TreeNodeLink) -> TreeNodeLink {
    if let Some(node) = root {
        while node.left.is_some() {
            node = node.left.as_ref().unwrap();
        }
        Some(node)
    } else {
        None
    }
}

fn node_successor(head: TreeNodeLink) -> TreeNodeLink {
    if let Some(node) = head {
        // 如果节点有右子树，后继节点为右子树最左侧节点
        if node.right.is_some() {
            return left_leaf(node.right.as_ref());
        }

        // 如果没有右子树，当前节点是父节点的右孩子，继续向上找
        let mut parent = node.parent;
        while parent.is_some && parent.left != node {
            node = parent;
            parent = node.parent;
        }
        // 当parent是空时，说明node是整棵树最右侧结点，没有后继节点
        return parent;
    } else {
        None
    }
}
*/

fn test_lca_recursion() {
    let s = "1_2_0_N_N_4_6_N_N_7_N_N_3_5_8_N_N_9_N_N_N";
    let root = create_bitree2(s);
    let node1 = find_node(&root, 6);
    let node2 = find_node(&root, 0);
    let node = find_lca_recursion(root.as_ref(), node1, node2);
    println!("除root外的公共节点(应该是2): {:?}", node);

    let node1 = find_node(&root, 6);
    let node2 = find_node(&root, 7);
    let node = find_lca_recursion(root.as_ref(), node1, node2);
    println!("除root外的公共节点(应该是4): {:?}", node);

    let node1 = find_node(&root, 8);
    let node2 = find_node(&root, 7);
    let node = find_lca_recursion(root.as_ref(), node1, node2);
    println!("公共节点(应该是1): {:?}", node);
}

fn print_recursion(curlevel: i32, level: i32, down: bool) {
    if curlevel > level {
        return;
    }
    print_recursion(curlevel + 1, level, true);
    if down {
        print!("凹");
    } else {
        print!("凸");
    }
    print_recursion(curlevel + 1, level, false)
}

fn print_all_folds(n: i32) {
    print_recursion(1, n, true);
}

pub fn test_treelink() {
    //let s = "1_2_4_N_N_5_N_N_3_6_N_N_7_N_N";
    let s = "1_2_N_4_6_N_N_7_N_N_3_5_8_N_N_9_N_N_N";
    let bts = "5_1_N_3_2_N_N_4_N_N_9_7_6_N_N_8_N_N_N";
    let root = create_bitree2(s);
    let bts_root = create_bitree2(bts);
    let mut res: Vec<i32> = vec![];
    println!("==========Rc<Box<TreeNode>>=========");
    preorder_recursion(&root, &mut res);
    println!("前序1遍历：{:?}", res);
    let res = preorder_unrecursion(&root);
    println!("前序2遍历：{:?}", res);
    let res = inorder_unrecursion(&root);
    println!("中序遍历：{:?}", res);
    let res = posorder_unrecursion1(&root);
    println!("后序遍历：{:?}", res);
    let res = width_traversial(&root);
    println!("宽度遍历：{:?}", res);
    let max_width = max_width_hash(&root);
    println!("最大宽度：{}", max_width);
    let max_width = max_width_unhash(&root);
    println!("最大宽度：{}", max_width);
    let res = is_bts_recursion(&root);
    println!("是搜索二叉树：{}", res);
    let res = is_bts_recursion(&bts_root);
    println!("是搜索二叉树：{}", res);
    let s = "1_2_4_N_N_5_N_N_3_6_N_N_7_N_N";
    let root = create_bitree2(s);
    let res = is_cbt_unrecursion(&root);
    println!("是完全二叉树：{}(true)", res);
    let s = "1_2_N_4_6_N_N_7_N_N_3_5_8_N_N_9_N_N_N";
    let root = create_bitree2(s);
    let res = is_cbt_unrecursion(&root);
    println!("是完全二叉树：{}(false)", res);
    let s = "1_2_0_N_N_4_6_N_N_7_N_N_3_5_8_N_N_9_N_N_N";
    let root = create_bitree2(s);
    let res = is_cbt_unrecursion(&root);
    println!("是完全二叉树：{}(false)", res);
    let res = is_fbts_unrecursion(&root);
    println!("[非递归] 是满二叉树：{}(false)", res);
    let res = is_fbts_recursion(&root);
    println!("[递归] 是满二叉树：{}(false)", res);
    let s = "1_2_4_N_N_5_N_N_3_6_N_N_7_N_N";
    let root = create_bitree2(s);
    let res = is_fbts_unrecursion(&root);
    println!("[非递归] 是满二叉树：{}(true)", res);
    let res = is_fbts_recursion(&root);
    println!("[递归] 是满二叉树：{}(true)", res);
    let res = is_balance(&root);
    println!("是平衡二叉树：{}(true)", res);
    let s = "1_2_0_N_N_4_6_N_N_7_N_N_3_5_8_N_N_9_N_N_N";
    let root = create_bitree2(s);
    let res = is_balance(&root);
    println!("是平衡二叉树：{}(false)", res);
    test_lca_unrecursion();
    test_lca_recursion();
    print_all_folds(3);
}
